﻿// 202. 最幸运的数字.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/204/

8  是中国的幸运数字，如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。

现在给定一个正整数 L，请问至少多少个 8 连在一起组成的正整数（即最小幸运数字）是 L 的倍数。

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含一个整数 L。

当输入用例 L=0 时，表示输入终止，该用例无需处理。

输出格式
每组测试用例输出结果占一行。

结果为 Case i:+一个整数 N，N 代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在，则 N=0。

数据范围
1≤L≤2×109
输入样例：
8
11
16
0
输出样例：
Case 1: 1
Case 2: 2
Case 3: 0
*/


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


typedef long long LL;

 
LL get_euler(LL C) {
	LL res = C;
	for (LL  i = 2; i <= C / i; i++) {
		if (C % i == 0) {
			while (C % i == 0) C /= i;
			res = res/i * (i - 1);
		}
	}
	if (C > 1) res = res / C * (C - 1);
	return res;
}

//龟速乘
LL qmul(LL a, LL b, LL c) {
	LL res = 0;
	while (b) {
		if (b & 1) res = (res + a) % c;
		a = (a + a) % c;
		b >>= 1;
	}
	return res;
}

LL qmi(LL a, LL k, LL b) {
	LL res = 1;
	while (k) {
		if (k & 1) {
			res = qmul(res, a, b);
		}
		a = qmul(a,a,b);
		k >>= 1;
	}

	return res;
}


//欧几里得算法
int gcd(LL a, int b) {
	return b ? gcd(b, a % b) : a;
}
int main()
{
	int T; T = 1;
	LL L;
	while (cin >> L, L) {
		int d = gcd(L, 8);
		LL C = 9 * L / d;
		LL phi = get_euler(C);

		LL res = 1e18;
		if (C % 2 == 0 || C % 5 == 0) res = 0;
		for (LL i = 1; i <= phi/i; i++) {
			if (phi % i == 0) {
				if (qmi(10, i, C) == 1) res = min(res, i);
				if (qmi(10, phi / i, C) == 1) res = min(res, phi/i);
			}
		}
		cout << "Case " << T++ << ": " << res << endl;
	}


	return 0;
}

